package com.github.hgkmail.hello.leetcode101.firstsearch;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//逆向思维：让海水蔓延进来，太平洋和大西洋的海水都能蔓延的格子就是满足条件的
public class LC417PacificAtlanticWaterFlow {
    //从边缘，沿着四个方向蔓延进来，
    public void dfs(int[][] heights, int[][] canReach, int i, int j, int prevH) {
        if (i<0 || i>=heights.length || j<0 || j>=heights[0].length || canReach[i][j]>0) {
            return;
        }
        int currH=heights[i][j];
        if (currH>=prevH) {
            canReach[i][j]=1;
            dfs(heights, canReach, i-1, j, currH);
            dfs(heights, canReach, i+1, j, currH);
            dfs(heights, canReach, i, j-1, currH);
            dfs(heights, canReach, i, j+1, currH);
        }
    }

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        if (heights.length<=0 || heights[0].length<=0) {
            return new ArrayList<>();
        }
        int m=heights.length;
        int n=heights[0].length;
        int[][] canReachPacific = new int[m][n];
        int[][] canReachAtlantic = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                canReachPacific[i][j]=0;
                canReachAtlantic[i][j]=0;
            }
        }
        for (int i = 0; i < m; i++) {
            dfs(heights, canReachPacific, i, 0, 0);
            dfs(heights, canReachAtlantic, i, n-1, 0);
        }
        for (int i = 0; i < n; i++) {
            dfs(heights, canReachPacific, 0, i, 0);
            dfs(heights, canReachAtlantic, m-1, i, 0);
        }
        //取重叠部分
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (canReachPacific[i][j]>0 && canReachAtlantic[i][j]>0) {
                    res.add(Arrays.asList(i,j));
                }
            }
        }

        return res;
    }

    public static void main(String[] args) {
        System.out.println(new LC417PacificAtlanticWaterFlow().pacificAtlantic(new int[][]{
                {1,2,2,3,5},{3,2,3,4,4},{2,4,5,3,1},{6,7,1,4,5},{5,1,1,2,4}
        }));
    }
}
